JZ37 数字在升序数组中出现的次数

https://www.nowcoder.com/practice/70610bf967994b22bb1c26f9ae901fa2

第一次解：

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        return binSearch(array, k);
    }
    
    public int binSearch(int[] arr, int target) {
        if (arr.length == 0) return 0;
        if (arr.length == 1) return arr[0] == target ? 1 : 0;
        
        int low = 0;
        int length = arr.length - 1;
        int high = arr.length - 1;
        int res = 0;
        
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] < target) {
                low = mid + 1;
            } else if (arr[mid] > target) {
                high = mid - 1;
            } else {
                res = 1;
                
                // 检查左边是否还有更小的数
                while (mid - 1 >= 0 && arr[mid - 1] == target) {
                    mid--;
                }
                
                while (mid + 1 <= length && arr[mid + 1] == target) {
                    mid++;
                    res++;
                }

                return res;
            }
        }

        return 0;
     }
}

第二次解：

上面那种解法极端情况下还是 $O(n)$

二分直接取得两边，注意看这 getLower、getUpper 的 if 条件不一样，携带了 = 号，会向另一边靠拢

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if (array.length < 1) return 0;
        if (array[array.length - 1] < k) return 0;

        int lower = getLower(array, k);
        int upper = getUpper(array, k);
        return upper - lower + 1;
    }
    
    int getLower(int[] array, int k) {
        int start = 0,end = array.length-1;
        int mid = (start + end)/2;
        while (start <= end) {
            if(array[mid] < k) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
            mid = (start + end)/2;
        }
        return start;
    }
    
    int getUpper(int[] array, int k) {
        int start = 0,end = array.length-1;
        int mid = (start + end)/2;
        while (start <= end) {
            if(array[mid] <= k) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
            mid = (start + end)/2;
        }
        return end;
    }
}